// @algorithm @lc id=85 lang=cpp 
// @title maximal-rectangle


#define print(...)
// @test([["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]])=6
// @test([])=0
// @test([["0"]])=0
// @test([["1"]])=1
// @test([["0","0"]])=0
class Solution {
public:
    int maximalRectangle(vector<vector<char>>& matrix) {
        int rows = matrix.size();
        if(0==rows) return 0;
        int cols = matrix[0].size();
        if(0==cols) return 0;
        vector<vector<int>> hmat(cols, vector<int>(rows, 0));
        for(int j=0; j<cols; j++){
            for(int i=0; i<rows; i++)
                if(0==j) hmat[j][i] = '1'==matrix[i][j];
                else hmat[j][i] = '1'==matrix[i][j] ? hmat[j-1][i]+1 : 0;
        }
        print("heights:\n", Mat(hmat))
        int ans = 0;
        for(auto & heights : hmat)
            ans = max(ans, largestRectangleArea(heights));
        return ans;
    }
    // LC-84. 柱状图中最大的矩形
    int largestRectangleArea(vector<int>& heights) {
        int n = heights.size();
        list<int> stk;
        vector<int> leftFirstShort(n, -1);
        for(int i=0; i<n; i++){
            while(stk.size() && heights[stk.back()] >= heights[i])
                stk.pop_back();
            if(stk.size())
                leftFirstShort[i] = stk.back();
            stk.push_back(i);
        }
        print("left:", leftFirstShort, "\n")
        
        stk.clear();
        vector<int> rightFirstShort(n, n);
        for(int i=n-1; i>=0; i--){
            while(stk.size() && heights[stk.back()] >= heights[i])
                stk.pop_back();
            if(stk.size())
                rightFirstShort[i] = stk.back();
            stk.push_back(i);
        }
        print("right:", rightFirstShort, "\n")

        int ans = 0;
        for(int i=0; i<n; i++)
            ans = max(ans, (rightFirstShort[i]-leftFirstShort[i]-1) * heights[i]);
        return ans;
    }
};